import math
import random
import copy
import numpy as np


# 定义一个函数Value，用于计算攻击数的评估值
def Value(state):
    # 初始化攻击值为0
    attack = 0
    # 遍历状态中的每一个元素
    for i in range(len(state)):
        # 遍历状态中的每一个元素
        for j in range(i + 1, len(state)):
            # 如果两个元素相等或者两个元素差值的绝对值等于两个元素下标的差值
            if state[i] == state[j] or \
                    abs(state[i] - state[j]) == abs(i - j):
                # 攻击值加1
                attack = attack + 1

    # 返回攻击值
    return attack


# 定义一个Problem类，用于初始化问题
class Problem():
    def __init__(self, start):
        self.InitialState = start


# 定义一个Node类，用于初始化节点
class Node():
    def __init__(self, state, Taboo=[]):
        self.State = state
        self.Value = Value(state)
        self.Taboo = Taboo  # `记录不能访问的邻居`

    def AllNeighbors(self):  # `所有可访问邻居`
        Nbs = []
        state = self.State
        for i in range(len(state)):
            for j in range(1, len(state)):
                s = copy.deepcopy(state)
                s[i] = (state[i] + j) % (len(state))
                if s not in self.Taboo:
                    Nbs.append(s)
        return Nbs

    def LowestSucessor(self):  # `目标值最小后继`
        Nbs = self.AllNeighbors()
        val = [Value(s) for s in Nbs]
        return Nbs[np.argmin(val)]

    def RandLowSucessor(self):  # `目标值比当前状态小的后继`
        Nbs = self.AllNeighbors()
        low = [s for s in Nbs if Value(s) < Value(self.State)]
        return self.State if len(low) == 0 \
            else random.choice(low)

    def RandSucessor(self):  # `随机后继`
        Nbs = self.AllNeighbors()
        return random.choice(Nbs) #随机取数组元素


# 定义一个GreedyHillClimbing函数，用于贪婪爬山法
def GreedyHillClimbing(problem):
    # 初始化当前节点为问题初始状态
    current = Node(problem.InitialState)
    # 循环爬山
    while True:
        # 计算当前节点的后继节点
        sucessor = Node(current.LowestSucessor())
        # 如果后继节点的值大于当前节点的值，则返回当前节点的状态
        if sucessor.Value >= current.Value:  # `局部最优`
            return current.State
        else:  # `下降的后继`
            current = sucessor
    return current


# 定义一个RandHillClimbing函数，用于随机爬山法
def RandHillClimbing(problem):
    # 初始化当前节点为问题初始状态
    current = Node(problem.InitialState)
    # 循环爬山
    while True:
        # 计算当前节点的后继节点
        sucessor = Node(current.RandLowSucessor())
        # 如果后继节点的值大于当前节点的值，则返回当前节点的状态
        if sucessor.Value >= current.Value:
            return current.State
        # 否则，当前节点等于后继节点
        current = sucessor


# 定义一个TranslationHillClimbing函数，用于翻译爬山法
def TranslationHillClimbing(problem, lim):
    # ` lim是允许侧向移动的次数`
    # 初始化计数器为0
    count = 0
    # 初始化禁忌表为空
    Taboo = []
    # 初始化当前节点为问题初始状态
    current = Node(problem.InitialState)
    # 循环爬山
    while True:
        # 计算当前节点的后继节点
        sucessor = Node(current.LowestSucessor(), Taboo)
        # 如果后继节点的值大于当前节点的值，则返回当前节点的状态
        if sucessor.Value > current.Value:  # `局部最优`
            return current.State
        # 如果后继节点的值等于当前节点的值，则判断计数器是否大于限制
        elif sucessor.Value == current.Value:  # `高原区的后继`
            if count > lim:
                return current.State
            else:
                # 否则，计数器加1，将当前节点添加到禁忌表中
                count += 1
                Taboo.append(current.State)
                # 当前节点等于后继节点
                current = sucessor
        else:  # `下降的后继`
            current = sucessor
            # 将禁忌表清空
            Taboo = []
            # 将计数器重置为0
            count = 0


# 定义一个SA函数，用于模拟退火法
def SA(problem, schedule):
    # 初始化最大迭代次数
    MAX = 1000
    # 初始化当前节点为问题初始状态
    current = Node(problem.InitialState)
    # 循环模拟退火
    for i in range(MAX):
        # 获取当前温度
        T = schedule[i]
        # 如果当前节点值小于1或者循环了1000次，则返回当前节点状态
        if current.Value < 1 or T < 1:
            return current.State
        # 计算当前节点的后继节点
        sucessor = Node(current.RandSucessor())

        # 计算当前节点和后继节点的差值
        dE = sucessor.Value - current.Value
        # 计算温度乘以差值的乘方
        P = math.exp(-dE / T)
        # 如果差值小于0或者随机数小于P，则当前节点等于后继节点
        if dE < 0 or random.random() < 0.1 * P:
            current = sucessor
    # 返回当前节点状态
    return current.State


if __name__ == '__main__':

    # 初始化温度范围
    schedule = range(1000, 0, -1)
    # 初始化计数器
    count = 0
    # 循环100次
    for i in range(100):
        # 初始化状态
        s = []
        # 初始化状态长度
        for i in range(8):
            # 随机生成一个0-7的数
            s.append(random.randint(0, 7))
        # 初始化问题
        p = Problem(s)
        # 调用RandHillClimbing函数，爬山
        # s=RandHillClimbing(p)
        # 调用SA函数，模拟退火
        # s=SA(p,schedule)
        # 调用GreedyHillClimbing函数，爬山
        # s=GreedyHillClimbing(p)
        # 调用TranslationHillClimbing函数，爬山
        # lim为最大移动的状态多少次
        s = TranslationHillClimbing(p, 100)


        # 如果攻击数等于0，则计数器加1
        if Value(s) == 0:
            count = count + 1
    # 输出计数器
    print(count)